1. Technical Field
This invention relates to information processors, and more particularly, to a neural network processor for solving assignment problems.
2. Discussion
Optimization problems, such as constrained assignment problems, are among the most difficult for conventional digital computers to solve. This is because assignment problems are generally not solvable with a single solution, but instead there may be a range of possible solutions of which the best solution is sought. Often, the processing technique requires one entity to be selected from among many and assigned to one and only one other entity in such a way as to force the entire assignment over all entities to be optimal in some sense. For example, where individual "costs" are assigned to each entity-to-entity mapping, the problem becomes one of minimizing the total cost.
Examples of assignment problems include optimal plot-to-track correlation processing, the Traveling Salesman Problem, optimal resource allocation, computerized tomography, multi-beam acoustic and ultrasound tracking, nuclear particle tracking, multi-sensor data fusion (deghosting) for angle-only (passive) objects detected by multiple sensors, etc. Of particular interest is the deghosting problem. This problem arises whenever objects are to be detected from angle-only data originating from multiple sensors. For example, the sensors may be radar, infrared, optical or other types of sensors. In such cases a single sensor provides a measurement that consists of the angle (azimuth) on which a target lies on a line-of-bearing. With two or more sensors, the location can be determined as the intersection of the two lines-of-bearing. However, with multiple targets, multiple lines-of-bearing will be seen at both sensors. Lines will cross and intersections will be formed at points where no target actually exists. These intersections are called ghosts.
To illustrate the severity of the problem, if ten targets are observed by two sensors, up to 100 intersections can be formed. Since there are only 10 targets that means 90 of the intersections will be ghosts. With 50 targets, 2,500 intersections and 2,450 ghosts could be formed. Since the sensors have no other information available, no further discrimination of targets can be made.
The addition of a third sensor might help to resolve the ambiguities since one would find targets at the intersection of three lines-of-bearing, or triple intersections. However, with measurement inaccuracies, three lines-of-bearing corresponding to a true target will not intersect at a single point but will define a triangular region. The problem then is to first determine which triangular regions have small enough areas that they might be targets, and then to sort out the true targets from the ghosts in a group where there are many more intersections than targets. While targets will generally have smaller areas, merely taking the smallest areas will not ensure that no ghosts will be chosen.
Some previous approaches to assignment problems, such as the deghosting problem, have emphasized solutions in software on general purpose computers. One disadvantage with software solutions to assignment problems, is that they require extensive algorithm development, massive computational power, and are exceedingly slow for real-time or near-real-time problems such as angle-only target location problems. This is because the deghosting problem is a non-deterministic polynomial complete (NP-complete) class problem, for which the computational requirements for conventional techniques increase exponentially as a function of the number of targets. As a result, the problem involves a "combinatorial explosion.revreaction., or exponential blowup in the number of possible answers. Thus, to solve the deghosting problem, conventional solutions, even using advanced state of the art array and parallel processors, have difficulty handling real-time problems of realistic sizes. For example, conventional solutions of the deghosting problem for three sensors are sufficiently fast up to about 15 targets, but become exponentially computation-bound beyond that. For numbers of targets in the range of 30 or so, typical software approaches using integer programming techniques could require virtually years of VAX-equivalent CPU time.
Others have suggested approaches for solving assignment problems utilizing neural networks. Such systems are called neural networks because of their similarity to biological networks in their highly interconnected structure and in their ability to adapt to data and exhibit self-learning. A key advantage of a neural network approach is that the network can be trained to solve the problem and an explicit algorithm does not have to be developed. For example, see U.S. Pat. No. 4,660,166, issued to J. Hopfield, where a type of neural network is used to solve the Traveling Salesman Problem. Others have suggested the use of a neural network technique known as simulated annealing. See S. Kirkpatrick, Gelatt, and Vecchi: 37 Optimization by Simulated Annealing", 220 Science, p. 671-680 (1983). However, while algorithms using this approach have been developed, to the applicant's knowledge, practical working architectures have not been implemented. Also, neural nets such as the one described in U.S. Pat. No. 4,660,166 are generally not fast enough for real-time applications of reasonable complexity. Recent results suggest severe limitations to the size of problems addressable by Hopfield nets. For example, the Traveling Salesman Problem has been found to fail for more than thirty cities. Also, even some neural network approaches use a network that embodies certain application constraints or use certain optimizing techniques. This results in greater complexity, and other limitations since the constraints must first be known and then the network configured to learn these constraints.
Thus it would be desirable to provide an information processor that reduces the computation time required to solve constrained assignment problems of realistic sizes in real-time.
It would also be desirable to provide an information processor that can solve such problems without requiring extensive algorithm development.
It would be desirable to provide an information processor to solve assignment problems which did not require explicit known constraints nor employ optimization techniques.